package cn.suchan.jianzhi.q52_regex;

import java.util.ArrayList;

/**
 * 知识点：正则表达式匹配
 * 题目描述
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
 * 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 *
 * @author suchan
 * @date 2019/06/10
 */
public class Solution {

    /**
     * 这个理解错*的意思了，但是先留着
     *
     * @param str
     * @param pattern
     * @return
     */
    public boolean match(char[] str, char[] pattern) {
        if ((str == null || str.length <= 0)
                && (pattern == null || pattern.length <= 0)) {
            return true;
        }

        if (str.length > 0
                && (pattern == null || pattern.length <= 0)) {
            return false;
        }

        if (str.length <= 0 && pattern.length <= 2 && pattern[pattern.length - 1] == '*') {
            return true;
        }

        int index = str.length - 1;
        int i = pattern.length - 1;
        for (; i >= 0 && index >= 0; i--) {
            if (pattern[i] != '*' && pattern[i] != '.' && pattern[i] != str[index]) {
                return false;
            } else if (pattern[i] == '*') {
                int startIndex = index;
                ArrayList<Character> temp = new ArrayList<>();
                for (; i > 0; i--) {
                    if (pattern[i - 1] != '*') {
                        temp.add(pattern[i - 1]);
                    } else {
                        break;
                    }
                }
                // aaa
                // ab*.*ac*
                int tempIndex = 0;
                while (index >= 0 && tempIndex < temp.size()) {
                    if (str[index] != temp.get(tempIndex) && temp.get(tempIndex) != '.') {
                        while (index + 1 < str.length && str[index + 1] != str[startIndex]) {
                            index++;
                        }
                        break;
                    }
                    index--;
                    tempIndex++;
                    if (index >= 0 && tempIndex == temp.size()) {
                        tempIndex = 0;
                    }
                }
            } else {
                index--;
            }
        }
        if (i < 0 && index < 0) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 这个是ok的，我觉得可以优化一些，写好看点，但是现在先不弄
     *
     * @param str
     * @param pattern
     * @return
     */
    public boolean match1(char[] str, char[] pattern) {
        if ((str == null || str.length <= 0)
                && (pattern == null || pattern.length <= 0)) {
            return true;
        }

        if (str.length > 0
                && (pattern == null || pattern.length <= 0)) {
            return false;
        }
        if (str.length <= 1 && pattern.length <= 2 && pattern[pattern.length - 1] == '*') {
            return true;
        }

        if (str.length > 0) {

            int index = str.length - 1;
            int i = pattern.length - 1;
            //
            for (; i >= 0 && index >= 0; i--) {

                if (pattern[i] != '*' && pattern[i] != '.' && pattern[i] != str[index]) {
                    return false;
                } else if (pattern[i] == '*') {
                    i--;
                    if (i >= 0 && pattern[i] == str[index]) {
                        index--;
                        while (index >= 0 && str[index] == str[index + 1]) {
                            index--;
                        }
                        if (index < 0) {
                            i--;
                            if (i >= 0 && pattern[i] == '*') {
                                index = 0;
                            }
                            while (i >= 0 && (pattern[i] == '.' || pattern[i] == str[0])) {
                                i--;
                            }
                            i++;
                        }
                    } else if (i >= 0 && pattern[i] == '.') {
                        while (i >= 0 && pattern[i] != '*') {
                            i--;
                        }
                        while (index >= 0 && str[index] != pattern[i + 1]) {
                            index--;
                        }
                    } else if (i == 0) {
                        index--;
                    }
                } else {
                    index--;
                }
            }
            if (i < 0 && index < 0) {
                return true;
            } else {
                return false;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.match1("aab".toCharArray(), "c*a*b".toCharArray()));
    }
}
